package algorithm.t202112;

import java.util.*;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/12/4 17:03
 * @description :4道
 * 停了半天的点（从早上9点到下午4点），才做了4道题，唉。现在做力扣已经300道题了，但感觉自己还是个小白，学习的路还很长很长，需要一步一步地踏实的走下去。
 今天看到一句话感觉很不错：青山原不老,为雪白头 绿水本无忧,因风皱面。很美的意境，再看看自己的文学水平，哈哈哈，算了算了。明天是星期天，一周又过去了，时间如
 流水，转瞬即逝，努力。
 persevere to last
 2021.12.4
 李红磊
 2021年12月4日21:24:30
 */
public class t20211204 {


    //101.对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return true;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root.left);
        queue.addLast(root.right);
        while (!queue.isEmpty()) {
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            if (left == null && right == null) continue;
            if (left == null || right == null) return false;
            if (left.val != right.val) return false;

            queue.addLast(left.right);
            queue.addLast(right.left);
            queue.addLast(left.left);
            queue.addLast(right.right);
        }

        return true;
    }

    //264.丑数2
    public int nthUglyNumber(int n) {
        int[] nums = {2, 3, 5};
        PriorityQueue<Long> queue = new PriorityQueue() {{
            add(1l);
        }};
        HashSet<Long> set = new HashSet<>();

        for (int i = 1; i <= n; i++) {
            long poll = queue.poll();
            if (n == i) return (int) poll;
            for (int item : nums) {
                long temp = item * poll;
                if (!set.contains(temp)) {
                    set.add(temp);
                    queue.add(temp);
                }
            }


        }
        return -1;
    }

    //96.不同的二叉搜索树
    public int numTrees(int n) {
        //卡特兰数
        int[] dp = new int[n + 1];//dp[i]:表示给定i节点值可以构成的BST树的数量
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }

    //97.交错字符串
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length();
        int n = s2.length();
        if (m + n != s3.length()) return false;
//dp[i][j]:表示s1的前i个字符和s2的前j个字符能成构成s3的前i+j个字符
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 1; i <= m && s1.charAt(i - 1) == s3.charAt(i - 1); i++) dp[i][0] = true;
        for (int j = 1; j <= n && s2.charAt(j - 1) == s3.charAt(j - 1); j++) dp[0][j] = true;


        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = (dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1) ||
                        dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1));
            }
        }
        return dp[m][n];
    }


    public static void main(String[] args) {
        t20211204 t20211204 = new t20211204();
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(2);
        root.left = node1;
        root.right = node2;


        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        node1.left = node3;
        node1.right = node4;

        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(3);
        node2.left = node5;
        node2.right = node6;

        System.out.println(t20211204.isSymmetric(root));


    }


}
